package practice;


import java.util.*;

public class BinaryTreePractice {

    // 新建结点类
    public class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    // 判断两棵树是否相同:
    // 遍历all结点 只要一遇到不同就停止  相当于前序遍历
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 这里会有遗漏的情况：因为有短路原则
        /*if(p==null && q==null) {
            return true;
        }
        if(p==null || q==null) {
            return false;
        }
        // 来到这儿说明p、q均不为null
        // 判断相等
        if(p==q) {
            isSameTree(p.left,q.left); //左节点比较
            isSameTree(p.right,q.right); // 右节点比较
        } else {
            return false;
        }
        return true;*/

        // 改正：
        if((p==null&&q!=null) || (p!=null&&q==null)) {
            return false;
        }
        // 来到这儿：要么都不为null 要么都为null
        // 注意：判断节点是不是相同：位置+值！！

        /*if(p!=q) {
            return false;
        }
        // 来到这儿：p==q
        if(p!=null && q!=null) {
            // 进行左右子树的递归判断
            isSameTree(p.left,q.left);
            isSameTree(p.right,q.right);
        }
        return true;*/

        // 修改：
        if(p==null && q==null) {
            return true;
        }
        // 来到这儿：均不为空，判断相等
        if(p.val!= q.val) {
            return false;
        }
        /*else {
            isSameTree(p.left,q.left);
            isSameTree(p.right,q.right);
        }
        return true;*/

        // 注意实际返回形式：
        return (isSameTree(p.left,q.left) && isSameTree(p.right,q.right));
    }


    // 是否为子树：
    // 是否是相同树 不是则进行是否为子树判断  注意一定要进行判空！
    // 如果节点相同，找左右子树：一旦遇到不相同就false
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // 错误！！
        /*isSameTree(root,subRoot);
        // 然后进行判空
        if(root==null || subRoot==null) {
            return false;
        }
        // 来到这儿：至少root不为空
        if(root.val!=subRoot.val) {
            return false;
        }
        return (isSubtree(root.left,subRoot.left) && isSubtree(root.right,subRoot.right));*/

        // 注意看下面的修改：
        if(root==null) {
            return false;
        }
        // 判空后判断
        if(isSameTree(root,subRoot)) {
            return true;
        }
        // 如果不相等，下一个节点去对子树根节点  如果对上就可以进入isSameTree判断
        if(isSubtree(root.left,subRoot)) {
            //isSameTree(root.left,subRoot);
            // 注意返回值！！！
            return true;
        }
        if(isSubtree(root.right,subRoot)) {
            //isSameTree(root.right,subRoot);
            return true;
        }
        // 来到这：都不满足
        return false;
    }


    // 二叉树的最大深度：
    public int maxDepth(TreeNode root) {
        // 其实就相当于层序遍历并记录：注意递归不在三目运算符中
        // 如何判断一层遍历结束
        if(root==null) {
            return 0;
        }
        // 返回是要判断左子树深还是右子树深
        int leftTree = maxDepth(root.left);
        int rightTree = maxDepth(root.right);
        return (leftTree>rightTree? (leftTree+1):(rightTree+1));
    }

    // 判断平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if(root==null) {
            return true;
        }
        // 返回是要判断左子树深还是右子树深
        int leftTree = maxDepth(root.left);
        int rightTree = maxDepth(root.right);

        // 为什么绝对值要小于等于1：平衡树的定义--每个结点的左右子树（子结点）高度相差<=1
        // 平衡：每个结点的左右子树相差不超过1 && 左右子树均平衡
        return ((Math.abs(leftTree-rightTree)<=1)
                && (isBalanced(root.left)) && (isBalanced(root.right)));

    }


    // 但是上面的方法时间复杂度：O(N^2)
    // 改进：边遍历边判断是否平衡，降低时间复杂度为O(n)

    public int maxDepth2(TreeNode root) {
        if (root==null) {
            return 0;
        }
        int leftTree = maxDepth2(root.left);
        int rightTree = maxDepth2(root.right);

        if(leftTree>=0 && rightTree>=0 && (Math.abs(leftTree-rightTree)<=1)) {
            return (Math.max(leftTree,rightTree)+1);
        } else {
            return -1;
        }
    }

    public boolean isBalanced2(TreeNode root) {
        return maxDepth2(root)>=0;
    }



    // 判断是否为对称二叉树：左右子树是否对称（注意：对称！=一样）

    // 左右子树作为参数 进行是否对称的判断
    public boolean isChildSymmetric(TreeNode leftTree, TreeNode rightTree) {
        // 一个空  都空 都不空（左右子树是否相等）
        if((leftTree==null && rightTree!=null) || (leftTree!=null && rightTree==null)) {
            return false;
        }
        if(leftTree==null && rightTree==null) {
            return true;
        }
        // 都不空
        if(leftTree.val!=rightTree.val) {
            return false;
        }
        // 如果相等，继续其左右子树的判断
        return isChildSymmetric(leftTree.left,rightTree.right) &&
                isChildSymmetric(leftTree.right,rightTree.left);
    }

    public boolean isSymmetric(TreeNode root) {
        // 情况：子树  全空、 一个空 都不空
        if(root==null) {
            return true;
        }
        return isChildSymmetric(root.left,root.right);
    }



    // 分层遍历：两次循环 + 依赖队列 （是否为空 && 队列大小）
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 最外层List是层数  第二层List：每层的节点数
        List<List<Integer>> ret = new ArrayList<>(); // 注意治理的声明！
        if(root == null) {
            return ret; // 注意返回的也是ret！！
        }
        Queue<TreeNode> queue = new LinkedList<>(); // 再注意这里！
        queue.offer(root); // 队列存储根节点！

        // 不空就进行循环：队列是否为空 每层大小是否>0
        while(!queue.isEmpty()) { // 判断的是队列 ：每一次存储的都是改成的节点
            // 进行每层节点个数获取：
            int size = queue.size();
            // 进行每层存储
            List<Integer> row = new ArrayList<>();
            while(size>0) {
                TreeNode cur = queue.poll(); //弹出栈顶元素
                size--;
                row.add(cur.val);   // 这里报错是因为节点的类型不匹配
                if(cur.left!=null) {
                    queue.offer(cur.left);
                }
                if(cur.right!=null) {
                    queue.offer(cur.right);
                }
            }
            // 来到这儿：说明二叉树已经的一层已经遍历结束 即将看队列中的下层
            ret.add(row);
        }
        // 队列为空 说明每一层都已经遍历结束
        return  ret;
    }



    // 最近公共祖先
    // 二叉搜索树：
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) {
            return null;
        }
        if(root==p || root==q) {
            return root;
        }
        //if((root.val<p.val && root.val>q.val) || (root.val>p.val && root.val<q.val))

        // 其实到这儿之后就有两种情况：都在同一边 or 一左一右
        TreeNode leftNode = lowestCommonAncestor(root.left,p,q); // 先进行左边寻找
        TreeNode rightNode = lowestCommonAncestor(root.right,p,q); // 再进行右边寻找
        // 进行情况的判断：
        if(leftNode!=null && rightNode!=null) {
            // 一左一右
            return root;
        } else if(leftNode!=null) {
            return leftNode;
        } else {
            return rightNode;
        }
    }


    // 方法2：使用两个栈 (栈：先进后出）
    // stackP:存根结点到p结点的所有结点   stackQ:存根结点到q结点的所有结点
    // 然后进行栈的大小比较，大的先出差个结点 然后再同时出并比较是否相等，首次相等的就是最近公共祖先！
    // 难点：如何找到根结点到指定结点的路径！
    // 补充：如果结点的值存在一样的情况，出栈就比较地址！！！（找不一样的比较）

    // 得到根结点到指定结点的路径并存储在栈中
    private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if(root==null || node==null) {
            return false;
        }
        // 来到这儿说明既不相等又不为空 就进行存储
        // 注意下面顺序不能颠倒：不管相不相等先入栈 入栈后才比较！！
        // （不然如果直接相等了就根本不会入栈！！）
        stack.push(root);
        if(root==node) {
            return true;
        }
        // 然后进行其左右子树的递归
        // 结点放入栈之后还要与指定结点进行比较，看是否相等，是否还有继续的必要
        boolean ret1 = getPath(root.left,node,stack);
        // 进行返回值接收并判断true
        // 不能判断false：因为还可能存在于右边 右边还没有进行比较!!
        if(ret1) {
            return true;
        }
        // 来到这儿说明：左边不等 则右边进行递归及比较
        boolean ret2 = getPath(root.right,node,stack);
        if(ret2) {
            return true;
        }
        // 此时：左右节点都没有找到node，则当前根节点要出栈 并且返回false
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || p==null || q==null) {
            // 只要其中一个结点为空就说明找不到
            return null;
        }
        // 来到这儿：说明 有进行寻找路径比较的意义
        Stack<TreeNode> stackP = new Stack<>();
        getPath(root,p,stackP);
        Stack<TreeNode> stackQ = new Stack<>();
        getPath(root,q,stackQ);
        int sizeP = stackP.size();
        int sizeQ = stackQ.size();
        if(sizeP<sizeQ) {
            int tmp = sizeQ-sizeP;
            // Q进行出栈已达到一样数量
            while(tmp!=0) {
                stackQ.pop();
                tmp--; // 不要忘记循环条件的改变！
            }
        } else {
            int tmp = sizeP-sizeQ;
            // Q进行出栈已达到一样数量
            while(tmp!=0) {
                stackP.pop();
                tmp--; // 不要忘记循环条件的改变！
            }
        }
        // 到这儿说明：此时两个栈中的元素个数一致
        // 循环进行比较:注意循环条件
        // 其实栈中存储的是结点，那么比较大小比较的是结点的地址
        while(!stackP.isEmpty() && !stackQ.isEmpty()) {
            if(stackP.peek() == stackQ.peek()) {
                return stackP.peek();
            } else {
                // 不相等就两个都弹出
                stackP.pop();
                stackQ.pop();
            }
        }
        // 如果来到这儿就说明不满足以上 即找不到
        return null;
    }




    // 二叉搜索树转换为双向链表:

    // 写一个中序遍历的方法：
    public TreeNode prev = null;
    public void midTravel(TreeNode root) {
        if(root==null) {
            return;
        }
        midTravel(root.left);
        //System.out.print(root.val + " ");
        // 前驱：其实就是之前遍历的节点（所以要记录当前结点以供下一次使用）
        // 每次递归的记录结点都是会变化的 所以变量定义在外面

        root.left = prev;
        // 注意这里要判断是否为空 首次为空 而为空时hi发生空指针异常！
        if(prev != null) {
            prev.right = root;
        }
        prev = root; // 就是进行当前结点的更新

        midTravel(root.right);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null) {
            return null;
        }
        // 要拿到双向链表头结点：从二叉树根结点一直沿着之前的中序遍历往左走，
        // 直到遇到某一个结点的左子树为空，则该结点就是所找的头结点
        midTravel(pRootOfTree);
        TreeNode head = pRootOfTree;
        while(head.left != null) {
            head = head.left;
        }
        return head;
    }




    // 从前序与中序遍历构造二叉树:
    // 中序遍历：根结点左边是左子树 右边是右子树！
    // 重新写一个方法：
    // 注意参数preIndex（标记前序遍历的下标），但是后续要经历递归，需要改变下标，但是作为参数就是类似于局部变量
    // 所以拿出来作为全局变量 减少参数
    public int preIndex = 0;
    private TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBegin, int inEnd) {
       // 判断左右子树是否还存在
        if(inBegin>inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]); // 前序遍历构建好根结点
         // 找中序遍历中的根结点位置
        int rootIndex = findInorderIndex(inorder,preorder[preIndex],inBegin,inEnd);
        preIndex++; // 前序遍历的下标将向后移
        // root的左右子树的构建:左子树也就是前序遍历的下一个结点
        // 注意参数：中序遍历的左子树的最大范围就是根结点的左边结点！
        root.left = buildTreeChild(preorder,inorder,inBegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inEnd);
        return root; // 返回建好的二叉树的根结点
    }
    // 找中序遍历中的根结点位置
    private int findInorderIndex(int[] inorder, int val, int inBegin, int inEnd) {
        for (int i = inBegin; i <= inEnd; i++) {
            if(val == inorder[i]) {
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root = buildTreeChild(preorder,inorder,0,inorder.length-1);
        return root;
    }




    // 从中序与后序遍历构造二叉树:
    public int postIndex ; // 注意其大小声明位置！
    private TreeNode buildTreeChild2(int[] inorder, int[] postorder, int inBegin, int inEnd) {
        // 判断左右子树是否还存在
        if(inBegin>inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]); // 后序遍历构建好根结点
        // 找中序遍历中的根结点位置
        int rootIndex = findInorderIndex2(inorder,postorder[postIndex],inBegin,inEnd);
        postIndex--; // 后序遍历的下标将向前移
        // root的左右子树的构建:右子树也就是后序遍历的前一个结点
        // 注意参数：中序遍历的左子树的最大范围就是根结点的左边结点！
        // 注意：后序遍历先右再左：所以注意以下范围修改！
        //（但是对于中序遍历永远是根左左子树 根右右子树）
        root.right = buildTreeChild2(inorder,postorder,rootIndex+1,inEnd);
        root.left = buildTreeChild2(inorder,postorder,inBegin,rootIndex-1);
        return root; // 返回建好的二叉树的根结点
    }
    // 找中序遍历中的根结点位置
    private int findInorderIndex2(int[] inorder, int val, int inBegin, int inEnd) {
        for (int i = inBegin; i <= inEnd; i++) {
            if(val == inorder[i]) {
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        postIndex = postorder.length-1; // √
        return (buildTreeChild2(inorder,postorder,0,inorder.length-1));
    }



    // 根据二叉树创建字符串：
    private void tree2strChild(TreeNode root,StringBuilder sb) {
        if(root==null) {
            return ;
        }
        // 来到这儿：非空 进行判断左子树
        sb.append(root.val);
        if(root.left!=null) {
            sb.append('(');
            // 然后进行递归
            tree2strChild(root.left,sb);
            sb.append(')');
        } else {
            // 左子树为空 需要判断右子树是否为空 来决定加不加括号！
            if(root.right==null) {
                return;
            } else {
                // 左空右不空
                sb.append("()"); // 给左
            }
        }
        // 右边单独给一个描述
        if(root.right==null) {
            return;
        } else {
            sb.append('('); // 给右
            tree2strChild(root.right,sb); //递归
            sb.append(')');
        }
    }
    public String tree2str(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        tree2strChild(root,sb);
        // 调用方法之后sb就改变
        return sb.toString(); // 注意这里的返回形式！！
    }




    // 非递归实现二叉树的前序遍历：
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        // 使用栈存储：
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        // 注意双层循环：否则如果左为空而右不为空时会出现错误！--重难点！！
        while(cur!=null || !stack.isEmpty()) {
            while(cur!=null) {
                // 入栈
                stack.push(cur);
                /* 这里可以没有打印 直接存到链表中
                // 打印
                System.out.print(cur.val + " ");*/
                // 加到链表中
                list.add(cur.val);
                cur = cur.left; // 左子树
            }
            // 来到这儿：左子树为空 弹出元素 看右子树
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return list;
    }



    // 二叉树的中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root==null) {
            return ret;
        }
        // 不为空：循环入栈--注意循环层数
        Stack<TreeNode> stack = new Stack<>();
        // 注意定义一个当前结点
        TreeNode cur = root;
        while(cur!=null || !stack.isEmpty()) {
            while ((cur!=null)) {
                stack.push(cur);
                // 不打印 而是走向左子树
                cur = cur.left;
            }
            // cur为空：弹出并打印（加到链表中）
            TreeNode top = stack.pop();
            ret.add(top.val);
            cur = top.right; // 走向右边
        }
        return ret;
    }


    // 非递归实现后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        if(root==null) {
            return ret;
        }
        // 非空--进行循环
        while(cur!=null || !stack.isEmpty()) {
            while(cur!=null) {
                stack.push(cur);
                cur = cur.left;
            }
            // 此时cur==null 获取栈顶元素但不弹出
            TreeNode top = stack.peek();
            // 判断右子树是否存在
            if(top.right==null || top.right==prev) {
                stack.pop();
                System.out.print(top.val + " ");
                ret.add(top.val);
                prev = top; // 一定要声明这个赋值！！ 记录之前的节点
            } else {
                cur = top.right;
            }
        }
        return ret;
    }


/*

    // 翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        // 反转：所有根结点的左右子树互换位置--递归
    }



    // 自底向上的层序遍历：
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
    }
*/

}
